package code.oldCode.dynamic;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DynamicString {

    /**
     * 5. 最长回文子串
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        int[][] dp = new int[len][len];
        int maxLen = 1;
        String ans = String.valueOf(s.charAt(0));
        // 长度为1，表示从i到i，一定是回文
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        // 长度为2，表示从i到i+1，判断是否为回文
        for (int i = 0; i < len - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = 1;
                maxLen = 2;
                ans = s.substring(i, i + 2);
            }
        }
        // 从长度为3开始
        for (int l = 3; l <= len; l++) {
            int begin = 0, end = l - 1;
            while (end < len) {
                if ((dp[begin + 1][end - 1] == 1 && s.charAt(begin) == s.charAt(end))) {
                    dp[begin][end] = 1;
                    if (end - begin + 1 > maxLen) {
                        maxLen = end - begin + 1;
                        ans = s.substring(begin, end + 1);
                    }
                }
                begin++;
                end++;
            }
        }
        return ans;
    }

    /**
     * 139. 单词拆分
     *
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        Set<String> wordDictSet = new HashSet<>(wordDict);
        // dp[i]表示字符串s前i个字符组成的字符串s[0..i-1]是否能被拆分
        boolean[] dp = new boolean[len + 1];
        // dp[0]表示空串
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }

    /**
     * 516. 最长回文子序列
     *
     * @param s
     * @return
     */
    public int longestPalindromeSubseq(String s) {
        // 先做1143.最长公共子序列：s与s.reverse()的最长公共子序列即为本题解
        // 以下为正常解法
        int len = s.length();
        char[] chars = s.toCharArray();
        int[][] dp = new int[len][len];
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                if (chars[i] == chars[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
            }
        }

        return dp[0][len - 1];
    }

    /**
     * 72. 编辑距离
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        if (word1.isEmpty() && word2.isEmpty())
            return 0;
        if (word1.isEmpty())
            return word2.length();
        else if (word2.isEmpty())
            return word1.length();

        int len1 = word1.length();
        int len2 = word2.length();
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        // 表示0-i,0-j替换需要次数
        int[][] dp = new int[len1][len2];
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = w1[i] == w2[j] ? 0 : 1;
                } else if (i == 0) {
                    dp[i][j] = w1[i] == w2[j] ? (j - i) : dp[i][j - 1] + 1;
                } else if (j == 0) {
                    dp[i][j] = w1[i] == w2[j] ? (i - j) : dp[i - 1][j] + 1;
                } else {
                    dp[i][j] = w1[i] == w2[j] ? dp[i - 1][j - 1] : Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }
        return dp[len1 - 1][len2 - 1];
    }

    /**
     * 712. 两个字符串的最小ASCII删除和
     *
     * @param s1
     * @param s2
     * @return
     */
    public int minimumDeleteSum(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        if (s1.isEmpty() && s2.isEmpty())
            return 0;
        else if (s1.isEmpty()) {
            int ans = 0;
            for (Character c : c2) {
                ans += c;
            }
            return ans;
        } else if (s2.isEmpty()) {
            int ans = 0;
            for (Character c : c1) {
                ans += c;
            }
            return ans;
        }
        int[][] dp = new int[len1][len2];
        // dp数组开new int[len1 + 1][len2 + 1]即可避免i == 0 j == 0时候的if判断，dp[0][0]表示""和""空字符串比
        boolean i_eq = false;
        boolean j_eq = false;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (i == 0 && j == 0) {
                    if (c1[i] == c2[j]) {
                        dp[i][j] = 0;
                        i_eq = true;
                        j_eq = true;
                    } else
                        dp[i][j] = c1[i] + c2[j];
                } else if (i == 0) {
                    if (c1[i] == c2[j] && !i_eq) {
                        dp[i][j] = dp[i][j - 1] - c2[j];
                        i_eq = true;
                    } else
                        dp[i][j] = dp[i][j - 1] + c2[j];
                } else if (j == 0) {
                    if (c1[i] == c2[j] && !j_eq) {
                        dp[i][j] = dp[i - 1][j] - c1[i];
                        j_eq = true;
                    } else
                        dp[i][j] = dp[i - 1][j] + c1[i];
                } else {
                    dp[i][j] = c1[i] == c2[j] ? dp[i - 1][j - 1] : Math.min(dp[i - 1][j] + c1[i], dp[i][j - 1] + c2[j]);
                }
            }
        }
        return dp[len1 - 1][len2 - 1];
    }

    public static void main(String[] args) {
        DynamicString dynamicString = new DynamicString();
        List<String> wordDict = new ArrayList<>();
        wordDict.add("aaaa");
        wordDict.add("aaa");
        System.out.println(dynamicString.minimumDeleteSum("sjfqkfxqoditw", "fxymelgo"));
    }
}
